#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
using namespace std;

void PrintMas(int A[], int n) {
    for (int i = 0; i < n; i++) {
        cout << A[i] << " ";
    }
    cout << endl;
}

void FillRand(int A[], int n) {
    for (int i = 0; i < n; i++) {
        A[i] = rand();
    }
}

int ShellSort(int A[], int n){
    int C = 0, M = 0;
    for(int h = n/2; h > 0; h /= 2){
        for(int i = h; i < n; i++){
            int temp = A[i];
            int j = i;
            while(j >= h && A[j - h] > temp){
                C++;
                A[j] = A[j - h];
                M++;
                j -= h;
            }
            A[j] = temp;
            M++;
        }
    }
    return M+C;
}

int Bsearch1(int A[], int n , int x){
    int L = 0, R = n-1, C = 0;
    bool Naiden = false;
    while (L<=R){
        int m = floor((L+R)/2);
        C++;
        if (A[m] == x) {
            Naiden = true;
            break;
        }
        C++;
        if (A[m] < x) {
            L = m + 1;
        } else {
                R = m - 1;
            }
    }
    return C;
}

int Bsearch2(int A[], int n, int x){
    int L = 0, R = n-1, C = 0;
    bool Naiden = false;
    while (L<R){
        int m = floor((L+R)/2);
        C++;
        if (A[m]<x){
            L = m + 1;
        } else {
            R = m;
        }
    }
    if (A[R] == x){
        Naiden = true;
    } else {
        Naiden = false;
    }
  return C;
}



int main(){
    setlocale(LC_ALL,"rus");
    srand(time(0));
    cout << setw(6) << "n" << setw(28) << "Сф 1 версия" << setw(20) << "Сф 2 версия" << endl;
    //100
    int n = 100;
    int *A = new int [n];
    FillRand(A,n);
    int index = rand()%n;
    int i = A[index];
    ShellSort(A,n);
    cout << setw(6) << n << setw(15) << Bsearch1(A,n,i) << setw(15) << Bsearch2(A,n,i)<< endl;
    delete [] A;

    //200
    n = 200;
    A = new int [n];
    FillRand(A,n);
    index = rand()%n;
    i = A[index];
    ShellSort(A,n);
    cout << setw(6) << n << setw(15) << Bsearch1(A,n,i) << setw(15) << Bsearch2(A,n,i)<< endl;
    delete [] A;

    //300
    n = 300;
    A = new int [n];
    FillRand(A,n);
    index = rand()%n;
    i = A[index];
    ShellSort(A,n);
    cout << setw(6) << n << setw(15) << Bsearch1(A,n,i) << setw(15) << Bsearch2(A,n,i)<< endl;
    delete [] A;

    //400
    n = 400;
    A = new int [n];
    FillRand(A,n);
    index = rand()%n;
    i = A[index];
    ShellSort(A,n);
    cout << setw(6) << n << setw(15) << Bsearch1(A,n,i) << setw(15) << Bsearch2(A,n,i)<< endl;
    delete [] A;

    //500
    n = 500;
    A = new int [n];
    FillRand(A,n);
    index = rand()%n;
    i = A[index];
    ShellSort(A,n);
    cout << setw(6) << n << setw(15) << Bsearch1(A,n,i) << setw(15) << Bsearch2(A,n,i)<< endl;
    delete [] A;

    //600
    n = 600;
    A = new int [n];
    FillRand(A,n);
    index = rand()%n;
    i = A[index];
    ShellSort(A,n);
    cout << setw(6) << n << setw(15) << Bsearch1(A,n,i) << setw(15) << Bsearch2(A,n,i)<< endl;
    delete [] A;

    //700
    n = 700;
    A = new int [n];
    FillRand(A,n);
    index = rand()%n;
    i = A[index];
    ShellSort(A,n);
    cout << setw(6) << n << setw(15) << Bsearch1(A,n,i) << setw(15) << Bsearch2(A,n,i)<< endl;
    delete [] A;

    //800
    n = 800;
    A = new int [n];
    FillRand(A,n);
    index = rand()%n;
    i = A[index];
    ShellSort(A,n);
    cout << setw(6) << n << setw(15) << Bsearch1(A,n,i) << setw(15) << Bsearch2(A,n,i)<< endl;
    delete [] A;

    //900
    n = 900;
    A = new int [n];
    FillRand(A,n);
    index = rand()%n;
    i = A[index];
    ShellSort(A,n);
    cout << setw(6) << n << setw(15) << Bsearch1(A,n,i) << setw(15) << Bsearch2(A,n,i)<< endl;
    delete [] A;

    //1000
    n = 1000;
    A = new int [n];
    FillRand(A,n);
    index = rand()%n;
    i = A[index];
    ShellSort(A,n);
    cout << setw(6) << n << setw(15) << Bsearch1(A,n,i) << setw(15) << Bsearch2(A,n,i)<< endl;
    delete [] A;

    return 0;
}
